package com.example.demo.arithmetic.algorithm.dynamic_programing;

import java.util.Arrays;
import java.util.List;

// 动态规划 关键是要找到递推公式
// 贝尔曼-福特算法求最短路径
public class BellmanFord {

    static class Edge {
        int from;
        int to;
        int weight;

        public Edge(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }


    public static void main(String[] args) {
        List<Edge> edges = List.of(
                new Edge(6, 5, 9),
                new Edge(4, 5, 6),
                new Edge(1, 6, 14),
                new Edge(3, 6, 2),
                new Edge(3, 4, 11),
                new Edge(2, 4, 15)
                ,
                new Edge(1, 3, 9),
                new Edge(1, 2, 7)

        );
        // dp[1]代表1定点的距离
        // f(v)表示从起点出发，到达v这个顶点的最短距离
        //    初始时
        //    f(v)=0 当v等于起点时
        //    f(v)=♾️ 当v不等于起点时 未知的距离 设置为无穷大
        //    之后

        //    from代表从哪儿来  to代表到哪儿去
        //    新      旧   所有from
        //    f(to)=min(f(to),f(from)+from.weight)

        //        初始情况
        int[] dp = new int[7];
        dp[1] = 0;
        for (int i = 2; i < 7; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        // 多轮循环
        for (int i = 0; i < 5; i++) {
            for (Edge edge : edges) {
                if (dp[edge.from] != Integer.MAX_VALUE) {
                    // dp[edge.from] = MAX_VALUE代表未知距离,没必要加
                    dp[edge.to] = Math.min(dp[edge.to], dp[edge.from] + edge.weight);
                }
            }
        }

        System.out.println(Arrays.toString(dp));

    }


}
